﻿#define _CRT_SECURE_NO_WARNINGS
#include "Finish.hpp"
using namespace std;
//数组：二分查找-有序数组查找
int Search(vector<int>& nums, int target)
{
    //定义左右边界
    size_t left = 0, right = nums.size() - 1;
    //设定查找的边界条件：采用[]法则应判断只要<=都是合法区间
    while (left <= right)
    {
        //找到区间中点
        size_t middle = (left + right) / 2;
        //case 1 目标小于中点元素->说明目标在中点左侧，更新右边界
        //左边界为闭区间则跳过中点选择下一左元素作边界
        if (nums[middle] > target)
        {
            right = middle - 1;
        }
        //case 2 目标大于中点元素->说明目标在中点右侧，更新左边界
        //右边界为闭区间则跳过中点选择下一右元素作边界
        else if (nums[middle] < target)
        {
            left = middle + 1;
        }
        //case 3 目标等于中点元素->找到目标元素位置，返回下标t
        else return middle;
    }
    //case fail 直到结束循环都未找到，那么说明没有该元素 
    return -1;
}

//数组：双指针(前后)-元素删除
int removeElement(vector<int>& nums, int val)
{
    size_t n = nums.size();
    int find_index = 0, refresh_index = 0;
    for (; find_index < n; ++find_index)
    {
        if (nums[find_index] != val)
        {
            nums[refresh_index++] = nums[find_index];
        }
    }
    return refresh_index;
}

//数组：双指针(左右)-非递减数组生成非递减平方数组
vector<int> sortedSquares(vector<int>& nums)
{
    size_t n = nums.size();
    int p_left = 0, p_right = n - 1;
    vector<int> retv(n, 0);
    int i = n - 1;
    while (p_left <= p_right)
    {
        int num_l = nums[p_left] * nums[p_left];
        int num_r = nums[p_right] * nums[p_right];
        if (num_l > num_r)
        {
            retv[i] = num_l;
            p_left++;
        }
        else
        {
            retv[i] = num_r;
            p_right--;
        }
        --i;
    }
    return retv;
};

//数组：滑动窗口-非负数组计算和>=aim的最短子串长度
int minSubArrayLen(int aim, vector<int>& nums)
{
    size_t n = nums.size();
    int min = n + 1;
    int left = 0;
    int sum = 0;
    for (int right = 0; right < n; ++right)
    {
        sum += nums[right];
        while (sum >= aim)
        {
            min = min < (right - left + 1) ? min : right - left + 1;
            sum -= nums[left++];
        }
    }
    if (min > n)min = 0;
    return min;
}


//数组：螺旋矩阵（非算法题）
vector<vector<int>> generateMatrix(int n)
{
    //首先创建一个n*n矩阵
    vector<vector<int>> ret(n, vector<int>(n));
    //把构建这个螺旋数组想象成一个贪吃蛇从（0,0）依次向左>向下>向右>向上...进行循环，直到填满
    //创建每一步移动的坐标点
    int i = 0, j = 0;
    //创建贪吃蛇运动的四个边界，遇到边界就要转向下一个方向，开区间则为（-1，n）
    int i_wall_u = -1; int i_wall_d = n;//i为行坐标，改变时影响上下方向，或二维数组列方向的运动
    int j_wall_l = -1; int j_wall_r = n;//j为列坐标，改变时影响左右方向，或二维数组行方向的运动
    int num = 1;//每走过一个位置需要填充的值， 更形象点可以理解为贪吃蛇每走一步在当前格时的总长
    //好像想象成吃豆人更合适，走一步得一分
    //这个循环可以最后给，先依次实现每一个方向运行一下看看
    while (num <= n * n)//我首先考虑的是一共n*n个元素，所以最终填充到num=n*n就说明可以结束了
        //查阅的资料给的是上下边界错位或左右边界错位就说明可以结束了，逻辑上更严谨
        //while(j_wall_l<=j_wall_r&&i_wall_u<=i_wall_d)
    {
        //这里是写到最后一个方向即向上运动时才补的
        //因为初始如果设置上边界为（-1，但实际上边界第一次时就走过0行了，所以上来就--
        i_wall_u++;//如果预设=0，那么应该可以移动到最后一行

        //1.向左运动
        while (j < j_wall_r)//只要每碰到墙就继续下一格，开区间所以是<》而非<=
        {
            ret[i][j] = num;//首先给当前位置赋值
            num++;//然后num++,为下一格赋值做准备
            j++;//然后列坐标增加，坐标（i,j）相对原位置左移一位
            //更简便的可以写为
            //ret[i][j++]=num++;
        }
        //因为是开区间列坐标在上次运动遇到边界后会=j_wall_r,另外i坐标还停在当前行
        i++; j--;//修正(i,j),i++是为了移动到下一位置准备向下运动
        j_wall_r--;//下次再遇到右边界就不是n,而是向内收缩一格
        //同理
        //2.向下运动
        while (i < i_wall_d)
        {
            ret[i][j] = num;
            num++;
            i++;
        }
        i--; j--; i_wall_d--;
        //3.向右运动
        while (j > j_wall_l)
        {
            ret[i][j] = num;
            num++;
            j--;
        }
        j++; i--; j_wall_l++;
        //4.向上运动
        while (i > i_wall_u)
        {
            ret[i][j] = num;
            num++;
            i--;
        }
        i++; j++;
    }
    return ret;

}

//数组：预处理思想 - 计算数组子串和(预处理思想)(非力扣)
void calcue_subarr_sum(int n)
{
    vector<int> nums(n);
    vector<int> nums_sumi(n);
    int sumi = 0;
    cout << "input " << n << " nums:";
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &nums[i]);
        //cin>>nums[i];
        sumi += nums[i];
        nums_sumi[i] = sumi;
    }
    int a = 0, b = 0;
    //while(cin>>a>>b)
    cout << "input a and b,from [0," << n - 1 << "],a<=b" << endl;
    while (~scanf("%d %d", &a, &b))
    {
        cout << "input a and b,from [0," << n - 1 << "],a<=b" << endl;
        if (a <= b && a < n && b < n && a >= 0 && b >= 0)
        {
            if (a == 0) cout << nums_sumi[b] << endl;
            else cout << nums_sumi[b] - nums_sumi[a - 1] << endl;
        }
        else
        {
            cout << "illegal address" << endl;
        }
        cout << "（ctrl+z ，enter ）* 3 will end"<<endl;
    }
}

//数组：预处理思想 - 计算二维数组二分后子集和的最小差值(非力扣)
void find_the_mindef_plan()
{
    cout << "Creat a n*m Matrix，input n and m" << endl;
    int n = 0, m = 0;
    cin >> n >> m;
    cout << "input " << n <<"*"<<m<< " nums:";
    vector<vector<int>> nums_nxm(n + 1, vector<int>(m + 1));
    int sumi = 0;
    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < m + 1; ++j) {
            scanf("%d", &nums_nxm[i][j]);
            nums_nxm[0][j] += nums_nxm[i][j];
            nums_nxm[i][0] += nums_nxm[i][j];
        }
    }
    for (auto a : nums_nxm)
    {
        Print_Vector(a, a.size());
    }
    vector<int> row_sum(n);
    vector<int> col_sum(m);
    int sum_r = 0;
    int sum_c = 0;
    for (int i = 1; i < n + 1; ++i) {
        sum_r += nums_nxm[i][0];
        row_sum[i - 1] = sum_r;
    }
    for (int i = 1; i < m + 1; ++i) {
        sum_c += nums_nxm[0][i];
        col_sum[i - 1] = sum_c;
    }
    int min_val = INT_MAX;
    for (int i = 0; i < n; ++i) {
        row_sum[i] = abs(row_sum[n - 1] - 2 * row_sum[i]);

        min_val = min_val < row_sum[i] ? min_val : row_sum[i];

    }
    for (int i = 0; i < m; ++i) {

        col_sum[i] = abs(col_sum[m - 1] - 2 * col_sum[i]);

        min_val = min_val < col_sum[i] ? min_val : col_sum[i];
    }

    cout <<"min_val = " << min_val << endl;
   
}

//数组：二分查找-查找有序数组元素返回索引，没有返回对应插入位置索引
int searchInsert(vector<int>& nums, int target)
{
    int n = nums.size();
    int left = 0;
    int right = n - 1;
    int addtype = 0;
    int middle = 0;
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (nums[middle] > target)
        {
            right = middle - 1;
            addtype = 0;
        }
        else if (nums[middle] < target)
        {
            left = middle + 1;
            addtype = 1;
        }
        else
        {
            return middle;
        }
    }
    return middle + addtype;
}

//数组：二分查找-查找非递减数组目标值最左边界
int findleftRange(vector<int>& nums, int target)//找最左下标
{
    int n = nums.size();
    int leftRange = -1;
    int left = 0;
    int right = n - 1;
    int middle = 0;
    while (left <= right)
    {
        middle = left + ((right - left) / 2);
        if (nums[middle] > target)//大于目标值，说明目标值在左侧，更新右边界
        {
            right = middle - 1;
        }
        else if (nums[middle] < target)//小于目标值，说明目标值在右侧，更新左边界
        {
            left = middle + 1;
        }
        //等于目标值比较特殊，因为要找最左下标,已找到的不一定是最左，左侧可能还有
        //所以同样更新右边界，同时将等于位置的下标暂时记录为最左
        else
        {
            right = middle - 1;//更新右边界
            leftRange = middle;//暂定为最左继续找左侧
            //在后面的循环中如果没有更左则一定不会在进入这个else
            //所以最后一次的最左保存值为最终值
            //如果又一次进来则会更新更左的下标
        }
    }
    return leftRange;
    //如果区间没有目标值那么寻找过程只会在if和else if中循环
    //leftRange不会被更新，保持-1传递出去
}
//数组：二分查找-查找非递减数组目标值最右边界
int findrightRange(vector<int>& nums, int target)
{
    int n = nums.size();
    int rightRange = -1;
    int left = 0;
    int right = n - 1;
    int middle = 0;
    while (left <= right)
    {
        middle = left + ((right - left) / 2);
        if (nums[middle] > target)
        {
            right = middle - 1;
        }
        else if (nums[middle] < target)
        {
            left = middle + 1;
        }
        else
        {
            left = middle + 1;
            rightRange = middle;
        }
    }
    return rightRange;
}
//数组：二分查找-查找非递减数组目标值最左或最右边界
int findBoundary(vector<int>& nums, int target, bool isLeft) 
{
    int n = nums.size();
    int boundary = -1;
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + ((right - left) / 2);
        if (nums[mid] > target) {
            right = mid - 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            boundary = mid;
            if (isLeft) {
                right = mid - 1; // 继续在左侧寻找左边界
            }
            else {
                left = mid + 1; // 继续在右侧寻找右边界
            }
        }
    }
    return boundary;
}
//数组：二分查找-查找非递减数组目标值最左和最右边界
vector<int> searchRange(vector<int>& nums, int target)
{
    int n = nums.size();
    vector<int> ret(2, -1);
    if (n == 0) return ret;

    int leftRange = findBoundary(nums, target, true);
    int rightRange = findBoundary(nums, target, false);
    ret[0] = leftRange;
    ret[1] = rightRange;
    return ret;
}

//数组：二分查找-判断一个数是否是完全平方数
bool isPerfectSquare(int num)
{
    if (num == 1)return true;
    int left = 1, right = num;
    int mid = 0;
    long long square = 0;
    while (left <= right)
    {
        mid = left + ((right - left) / 2);//防止溢出
        square = (long long)mid * mid; //防止溢出
        if (square < num)
        {
            left = mid + 1;
        }
        else if (square > num)
        {
            right = mid - 1;
        }
        else
        {
            return true;
        }
    }
    return false;
}